package com.leetcode.binary_search;

/**
 * @author Dennis Li
 * @date 2020/7/24 18:23
 */
public class RotatedSortedArray_153 {

    public int findMin(int[] nums) {
        int len = nums.length - 1;
        if (nums.length == 1) return nums[0];
        int min = 0, i = 0, j = len;
        for (; i < j; i++, j--) {
            if (nums[i] > nums[i + 1]) {
                min = i + 1;
                break;
            } else if (nums[j] < nums[j - 1]) {
                min = j;
                break;
            }
        }
        return nums[min];
    }

    public int findMin2(int[] nums) {
        int len = nums.length - 1;
        if (nums.length == 1 || nums[0] < nums[len]) return nums[0];
        int mid, i = 0, j = len;
        while (i < j) {
            mid = i + (j - i) / 2;
            if (nums[mid] > nums[j]) {
                i = mid + 1;
                if (nums[i] < nums[mid]) {
                    j = mid;
                    break;
                }
            } else {
                j = mid - 1;
                if (nums[j] > nums[mid]) {
                    j = mid;
                    break;
                }
            }
        }
        return nums[j];
    }

    public int findMin3(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int middle = (left + right) / 2;
            if (nums[middle] < nums[right]) {
                // middle可能是最小值
                right = middle;
            } else {
                // middle肯定不是最小值
                left = middle + 1;
            }
        }
        return nums[left];
    }

    static class Solution {

        public int findMin2(int[] nums) {
            int left = 0, right = nums.length - 1;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] <= nums[right]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return nums[right];
        }

        public int findMin(int[] nums) {
            int i = 0, j = nums.length;
            int left = nums[0], right = nums[j - 1];
            // 数组不超过2的情况下的特殊处理
            // 如果末尾大于开头，代表没有旋转
            if (left < right) return left;
            // 检测是不是对第一位进行了旋转
            if (j > 1 && right < nums[j - 2]) return right;
            // 之所以是j - 1是为了避免出现 i = j - 1的情况，会陷入死循环
            while (i < j - 1) {
                int mid = i + (j - i) / 2;
                // 循环的退出条件
                if (mid > 0 && mid < nums.length && nums[mid] < nums[mid - 1] && nums[mid] < nums[mid + 1]) {
                    return nums[mid];
                }
                if (nums[mid] > left) {
                    i = mid;
                } else if (nums[mid] < right) {
                    j = mid;
                }
            }
            return nums[i];
        }
    }

}
